package com.veal98.bactrack;

import java.util.ArrayList;
import java.util.List;

public class LC216 {

    // 存储所有组合
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        if (k > 9) {
            return res;
        }

        List<Integer> track = new ArrayList<>();
        int start = 1;
        backtrack(k, n, start, track);
        return res;
    }

    /**
     * 在 {1,2,3,4,5,6,7,8,9} 这个集合中，找到相加之和为 n 的 k 个数的总和
     * @param start 标志位：从哪个位置开始做选择
     */
    private void backtrack(int k, int n, int start, List<Integer> track) {
        // tract 中所有元素的和
        int sum = 0;
        for (int i : track) {
            sum += i;
        }

        // 结束条件
        if (track.size() == k && sum == n) {
            res.add(new ArrayList<>(track));
            return;
        }

        // 遍历选择列表
        for (int i = start; i <= 9; i ++) {
            // 剪枝
            if (track.contains(i)) {
                continue;
            }

            // 做选择
            track.add(i);
            // 进入下一层解空间树
            backtrack(k, n, i + 1, track);
            // 回溯
            track.remove(track.size() - 1);
        }
    }

}
